package lbj.cyw.dp;
/*
* 32. 最长有效括号
*
*   只考虑为 ) 的情况
*   最后一步怎么来的一定要思考清楚!!!!!!
*
* */
public class LongestValidParentheses32 {
    public int longestValidParentheses(String s) {
        if(s.length()==0){
            return 0;
        }
        int max=0;
        int[] dp=new int[s.length()];
        dp[0]=0;
        for(int i=1;i<s.length();i++){
            if(s.charAt(i)==')'){
                if(s.charAt(i-1)=='('){
                    dp[i]=(i>=2?dp[i-2]:0)+2;
                }else if(i-dp[i-1]>0 && s.charAt(i-dp[i-1]-1)=='('){
                    // 前面的+中间的+新增的2
                    dp[i]=dp[i-1]+(i-dp[i-1]>=2?dp[i-dp[i-1]-2]:0)+2;
                }
                max=Math.max(max,dp[i]);
            }
        }
        return max;
    }
}
